'''
https://leetcode.cn/problems/distinct-subsequences/description/
'''
from functools import cache


class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(s), len(t)

        @cache
        def f(i, j):
            if j == n:
                return 1
            if i == m:
                return 0
            if m - i < n - j:   #剪枝 3 in [0, 5]  0 in [0, 3]
                return 0
            res = 0
            for k in range(i, m):
                if s[k] == t[j]:
                    res += f(k + 1, j + 1) % MOD
            return res % MOD
        return f(0, 0)
    def numDistinct2(self, s: str, t: str) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(s), len(t)
        # 依赖 (右一个)(下方n个格子)  从右往左填就行
        dp = [[0] * (n) + [1] for _ in range(m + 1)]
        for j in range(n-1, -1, -1):
            # for i in range(m):  # i == m then dp[i][j] = 0
                # if m - i < n - j:  # 剪枝 3 in [0, 5]  0 in [0, 3]
                #     continue
            # m - i >= n - j   => m - n + j >= i => i <= m - n + j
            for i in range(0, m - n + j + 1):
                res = 0
                for k in range(i, m):
                    if s[k] == t[j]:
                        res += dp[k+1][j+1] % MOD
                dp[i][j] = res % MOD
        return dp[0][0]

    # 第二种尝试方案
    def numDistinct3(self, s: str, t: str) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(s), len(t)

        @cache
        def f(i, j):
            if j == n:
                return 1
            if i == m:
                return 0
            res = f(i+1, j) % MOD
            if s[i] == t[j]:
                res += f(i+1, j + 1) % MOD
            return res
        return f(0, 0)

    def numDistinct4(self, s: str, t: str) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(s), len(t)
        dp = [[0] * (n) + [1] for _ in range(m + 1)]
        # 优化
        for i in range(m - 1, -1, -1):
            for j in range(n-1, -1, -1):
                dp[i][j] = dp[i + 1][j]
                if s[i] == t[j]:
                    dp[i][j] = (dp[i][j] + dp[i+1][j+1]) % MOD
        return dp[0][0]

s = 'rabbbit'
t = 'rabbit'
print(Solution().numDistinct3(s, t))